package it.storm.solution;

import java.util.*;

/**
 * 384. 打乱数组
 * https://leetcode-cn.com/problems/shuffle-an-array/
 */
public class Solutions_384 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution obj = new Solution(nums);
        int[] res1 = obj.shuffle();
        System.out.println(Arrays.toString(res1));
        int[] res2 = obj.reset();
        System.out.println(Arrays.toString(res2));
        int[] res3 = obj.shuffle();
        System.out.println(Arrays.toString(res3));
        int[] res4 = obj.reset();
        System.out.println(Arrays.toString(res4));
        int[] res5 = obj.shuffle();
        System.out.println(Arrays.toString(res5));
    }
}

/**
 * 解法二：Fisher-Yates 洗牌算法（97ms）
 */
class Solution {
    int[] nums;
    Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        // 深拷贝，避免修改 array 时，导致 originArr 也修改了
        int[] res = nums.clone();
        int len = res.length;
        // 倒序遍历，每个元素与其前面的某个随机元素进行交换
        for (int i = 0; i < len; i++) {
            // 将 array 数组中的索引 i 上的元素与 (i, array.length) 区间中的
            // 某个随机索引上的元素，进行交换
            int idx = random.nextInt(i + 1);
            if (idx == i) {
                continue;
            }
            // 元素替换
            int temp = res[idx];
            res[idx] = res[i];
            res[i] = temp;
        }
        return res;
    }
}

/**
 * 解法一：列表随机取值（97ms）
 */
class Solution2 {
    // 打乱数组时，记录在 array 中
    int[] array = null;
    // 始终记录的是源数组，即重置时返回的数组
    int[] originArr = null;

    public Solution2(int[] nums) {
        array = nums;
        // 深拷贝，避免修改 array 时，导致 originArr 也修改了
        originArr = nums.clone();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originArr;
    }

    private List<Integer> list = new ArrayList<>();
    private Random random = new Random();
    // arr 数组添加到 list 列表中（list 列表每次都是个空的列表）
    public void arrayToList(int[] arr) {
        list.clear();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        // 数组元素添加到 list 中，方便进行移除元素的操作
        arrayToList(originArr);
        for (int i = 0; i < array.length; i++) {
            // 随机索引取值：[0, list.size)
            int index = random.nextInt(list.size());
            array[i] = list.get(index);
            // 移除 index 索引上的元素，列表元素减少
            list.remove(index);
        }
        return array;
    }
}
